package com.azure.code.fibo;

import java.util.HashMap;
import java.util.Map;

/**
 * 爬楼梯
 * https://leetcode-cn.com/problems/climbing-stairs/
 */
public class ClimbStairs_70 {
    // 备忘录
    private Map<Integer, Integer> map = new HashMap<>();

    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if(map.get(n)!=null){
            return map.get(n);
        }
        int r = climbStairs(n-1) + climbStairs(n-2);
        map.put(n,r);
        return r;
    }

    public static int climbStairs_iter(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int prePre = 1,pre = 1;
        int result = 0;
        for (int i = 3; i <=n; i++) {
            result = pre + prePre;
            prePre = pre;
            pre = result;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(climbStairs_iter(4));
    }
}
